While MIMO systems offer the possibility of increasing data throughput without increasing bandwidth, the fact that a signal is sent via multiple antennas and/or received at multiple antennas make signal detection computationally complex as compared to systems employing a single transmit and single receive antenna. Specifically, the transmitted signal x is subject to interference and noise while moving through the wireless channel. The received signal y is detected and its value is determined by removing channel influences so as to resolve the best estimate of what the transmitted signal x was. Algebraically, y=Hx+n, where H is the channel matrix and n is noise. Channel influences are determined from measured or estimated parameters of the channel to determine the channel matrix H. In a single antenna system (one transmit and one receive antenna), there is one channel between them (neglecting multi-path detection) and H is one row. Where the received signal y is received over multiple channels such as when sent from multiple transmit antennas and/or received at multiple receive antennas, the channel is more than additive as H expands in rows and columns, so the corresponding computations involved to determine and remove influences from those multiple channels from that same single signal increases non-linearly with the number of antennas. To resolve the received signal y in a MIMO system, with the same confidence level (bit error rate) as for a single channel, a complex and iterative process many times more demanding than the baseline single channel scenario is employed. In that wireless systems use portable transceivers with a limited power supply and reduced/slower computational capacity as compared to larger, fixed and AC-powered base station transceivers, the theory of increased MIMO data rates is somewhat frustrated by these practical limitations of the mobile equipment that would most likely benefit from it.
Consider one prior art technique that may be used for MIMO signal detection, shown in FIG. 1, taken from FIG. 3a of U.S. Pub. No. 2005/0175122 A1, by Nikolai Nefedov et al.). As detailed in that publication, FIG. 3a illustrates a simplified flowchart of a sphere decoder signal detection method, and for simplicity assumes the same number of transmit and receive antennas Nt. A counter i is initialized 301 and the transmitted symbol xi is determined 302 in a reduced complexity sphere decoder by taking into account its modulation 302a and a priori reliability information concerning the transmitted symbol xi 302b. The sphere decoder is reduced complexity because it does not search the entire signal constellation or lattice but only a spherical subset thereof to resolve the symbol xi. The modulation scheme typically affects the area of the sphere in which the sphere decoder searches for the value of the symbol xi. The a priori information may be obtained from a channel decoder or error detector operating on the present symbol xi, from a previously detected symbol, or from an external source such as a channel decoder or error detector of another user or service. The determined symbol xi remains a soft value until all symbols xi are determined, in which case they are assembled into a vector x and output 305 as a hard output for which reliability information is determined 306.
The Nefedov publication describes that in estimating xi, upper and lower bounds to the estimated symbol xi as set forth in Eqs. 6-8 are recursively and iteratively updated by Eq. 9 until either a value of xi is determined or the search for xi begins again with a different initial parameter of xi−1. One can see that this may be a computationally intensive undertaking. Where the received symbols are voice, symbol decoding must be done in real time or nearly so. Where the received symbols are large data files (e.g., video or image data), symbol decoding need not be in the chronological order transmitted but there is typically a much larger volume of symbols to detect.
Apart from Nefedov's searching within a limited sphere that is less than the entire signal constellation, lattice reduction is one way to reduce this computational intensity. Specifically, lattice reduction in a MIMO detection system calculates a change of a basis matrix T for the channel H, such that H*T is closer to an orthogonal matrix than H. The change of basis matrix T is a unimodular integer matrix, meaning that its elements are only integers and its determinant DET(T)=±1. The MIMO symbol detection can then be performed by operating with H*T and T−1x, instead of H and x, where x is the transmitted symbol vector. The near orthogonality property of H*T results in relatively small noise enhancement with linear detection techniques (Zero Forcing, Minimum Mean Square Error), and so good detection performance is maintained. Lattice reduction can also be used to improve the performance of low complexity non-linear MIMO detectors such as Serial Interference Cancellation (SIC) detectors.
One way to calculate the change of basis matrix T is with the Lenstra-Lenstra-Lovasz (LLL) algorithm. The LLL algorithm is particularly detailed in a paper entitled FACTORING POLYNOMIALS WITH RATIONAL COEFFICIENTS by A. K. Lenstra, H. W. Lenstra and L Lovasz, in Math Ann 261, 515-534 (1982), hereby incorporated by reference. The LLL algorithm is widely used in the wireless communication arts, but under certain conditions it too might impose a high computational burden.
What is needed in the art is a symbol detection method and apparatus that operates with reduced complexity as compared to the prior art so as to be viable for power consumption, computational capacity, and time to resolve the received symbols in mobile platforms operating in a MIMO system.